// Created by WXX on 2021/10/22 20:27
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * 执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户
 * 内存消耗：6 MB, 在所有 C++ 提交中击败了23.54%的用户
 */
class Solution {
public:
    string getPermutation(int n, int k) {

        vector<int> f(n);
        f[0] = 1;
        for (int i = 1; i < n; i++) f[i] = f[i - 1] * i;

        vector<bool> st(n, false);
        string res;
        for (int i = 0; i < n; i++) {
            for (int j = 1; j <= n; j++) {
                if (st[j]) continue;

                if (f[n - 1 - i] < k) k -= f[n - 1 - i];
                else {
                    res += to_string(j);
                    st[j] = true;
                    break;
                }
            }
        }
        return res;
    }
};

int main() {

    cout << Solution().getPermutation(3, 5) << endl;  // 312

    return 0;
}
